//<p>给定数组
// <meta charset="UTF-8" />&nbsp;<code>people</code>&nbsp;。<code>people[i]</code>表示第 <code>i</code><sup>&nbsp;</sup>个人的体重&nbsp;，<strong>船的数量不限</strong>，每艘船可以承载的最大重量为&nbsp;<code>limit</code>。</p>
//
//<p>每艘船最多可同时载两人，但条件是这些人的重量之和最多为&nbsp;<code>limit</code>。</p>
//
//<p>返回 <em>承载所有人所需的最小船数</em>&nbsp;。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>people = [1,2], limit = 3
//<strong>输出：</strong>1
//<strong>解释：</strong>1 艘船载 (1, 2)
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>people = [3,2,2,1], limit = 3
//<strong>输出：</strong>3
//<strong>解释：</strong>3 艘船分别载 (1, 2), (2) 和 (3)
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>people = [3,5,3,4], limit = 5
//<strong>输出：</strong>4
//<strong>解释：</strong>4 艘船分别载 (3), (3), (4), (5)</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= people.length &lt;= 5 * 10<sup>4</sup></code></li> 
// <li><code>1 &lt;= people[i] &lt;= limit &lt;= 3 * 10<sup>4</sup></code></li> 
//</ul>
//
//<div><li>👍 313</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<vector<int>> rec;
    vector<int> val;

public:
    int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = max(rec[left][right], sum);
        }
        return rec[left][right];
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        val.resize(n + 2);
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec.resize(n + 2, vector<int>(n + 2, -1));
        return solve(0, n + 1);
    }
};
//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    //vector<int> data{7, 1, 5, 3, 6, 4};
    //auto ans = s.twoSum(data,11);
    //cout<<endl;
}